package leetcode.editor.algorithms;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int length = 10;
        int[] nums = new int[]{5,3,4,82,65,2,34,65,23,45};

        quickSort(nums,0,nums.length-1);
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
    public static void quickSort(int [] nums,int start,int end) {
        if (start>=end)
            return;
        //寻找基准数据的正确索引
        int index = partition(nums,start,end);
        //进行迭代，对index之前和之后的数组进行相同的操作使整个数组有序
        quickSort(nums,start,index-1);
        quickSort(nums,index+1,end);
    }
    public static int partition(int [] nums,int start,int end) {
        //基准数据
        int pivot = nums[start];
        int left  = start;
        int right = end;
        while (left<right) {
            //当对尾元素大于等于基准数据的时候，向前移动right指针
            while (left<right&&nums[right]>=pivot)
                break;
            //如果对尾元素小于基准数据的时候，将其赋值给left
            nums[left] = nums[right];

//            当对首元素小于等于基准数据时候，向后移动left指针
            while (left<right&&nums[left]<=pivot)
                left++;

            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

}
